#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    vector<int> tmp;
    vector<int> sortArray(vector<int>& nums) {
        tmp.resize(nums.size());
        mergeSort(nums, 0, nums.size() - 1);
        return nums;
    }

    void mergeSort(vector<int>& nums, int left, int right)
    {
        if (left >= right) return;
        int mid = (left + right) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        int cur1 = left, cur2 = mid + 1, i = 0;
        while (cur1 <= mid && cur2 <= right)
        {
            tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
        }
        while (cur1 <= mid)
        {
            tmp[i++] = nums[cur1++];
        }
        while (cur2 <= right)
        {
            tmp[i++] = nums[cur2++];
        }

        for (int i = left; i <= right; i++)
        {
            nums[i] = tmp[i - left];
        }

    }
};

class Solution2 {
public:
    vector<int> tmp;
    int reversePairs(vector<int>& nums) {
        tmp.resize(nums.size());
        return mergeSort(nums, 0, nums.size() - 1);

    }

    int mergeSort(vector<int>& nums, int left, int right)
    {
        if (left >= right) return 0;
        int ret = 0;
        int mid = (left + right) / 2;
        ret += mergeSort(nums, left, mid);
        ret += mergeSort(nums, mid + 1, right);
        int cur1 = left, cur2 = mid + 1, i = 0;
        while (cur1 <= mid && cur2 <= right)
        {
            if (nums[cur1] <= nums[cur2])
            {
                tmp[i++] = nums[cur1++];
            }
            else
            {
                ret += mid - cur1 + 1;
                tmp[i++] = nums[cur2++];
            }
        }
        while (cur1 <= mid)
        {
            tmp[i++] = nums[cur1++];
        }
        while (cur2 <= right)
        {
            ret += mid - cur1 + 1;
            tmp[i++] = nums[cur2++];
        }

        for (int j = left; j <= right; j++)
        {
            nums[j] = tmp[j - left];
        }

        return ret;
    }
};

class Solution3 {
public:
    vector<int> ret;
    vector<int> tmpNums;
    vector<int> index;
    vector<int> tmpIndex;

    vector<int> countSmaller(vector<int>& nums) {
        int n = nums.size();
        ret.resize(n);
        tmpNums.resize(n);
        index.resize(n);
        tmpIndex.resize(n);
        for (int i = 0; i < n; i++)
        {
            index[i] = i;
        }
        mergeSort(nums, 0, n - 1);
        return ret;
    }

    void mergeSort(vector<int>& nums, int left, int right)
    {
        if (left >= right) return;
        int mid = (left + right) / 2;

        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);

        int cur1 = left, cur2 = mid + 1, i = 0;
        while (cur1 <= mid && cur2 <= right)
        {
            if (nums[cur1] <= nums[cur2])
            {
                tmpNums[i] = nums[cur2];
                tmpIndex[i++] = index[cur2++];
            }
            else
            {
                ret[index[cur1]] += right - cur2 + 1;
                tmpNums[i] = nums[cur1];
                tmpIndex[i++] = index[cur1++];
            }
        }
        while (cur1 <= mid)
        {
            tmpNums[i] = nums[cur1];
            tmpIndex[i++] = index[cur1++];
        }
        while (cur2 <= right)
        {
            tmpNums[i] = nums[cur2];
            tmpIndex[i++] = index[cur2++];
        }

        for (int j = left; j <= right; j++)
        {
            nums[j] = tmpNums[j - left];
            index[j] = tmpIndex[j - left];
        }

    }
};

class Solution4 {
public:
    int reversePairs(vector<int>& nums) {

    }
};

int main()
{
    vector<int> nums = { 5,2,6,1 };
    Solution3 s;
    vector<int> ret;
    ret = s.countSmaller(nums);
    for (auto x : ret)
    {
        cout << x << " ";
    }

    return 0;
}

